For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

0
votes
0answers
19 views

Can you partition a rectangle into exactly 3 congruent non-rectangular parts?

Recently I came upon the following result: Theorem (*): Let $n$ be a positive integer not equal to $1,3,5,7,9$. Then it is possible to partition a rectangle into exactly $n$ congruent non-rectangular ...
3
votes
1answer
174 views

Number of ways to add multiples of numbers from a set of k numbers while all numbers are never multiplied.

I am trying to come up with a general formula. First let me give a simple example. Let there be 3 numbers: a, b, and c. I multiply any two of them to get: 1. a*b 2. b*c 3. c*a .......[A] Exactly ...
5
votes
1answer
112 views

Evaluate complicated sum

Evaluate following sum: $$\sum_{1\leqslant i< j \leqslant m}\sum_{\substack{1\leqslant k,l \leqslant n\\ k+l\leqslant n}} {n \choose k}{n-k \choose l}(j-i-1)^{n-k-l}.$$ Hint: use combinatorial ...
0
votes
1answer
40 views

Counting and Probability String Length

Consider strings that can be made up from the set $\{a, b, c, d, e, f, \cdots, z, 0, 1, 2, \cdots, 9\}$ 1) How many strings of length 8 contain either the letter '$x$' or '$1$'? 2) What is the ...
2
votes
1answer
24 views

Family of sets without 2 disjunct elements, prove the statement

Suppose, that the $F \subseteq 2^{[n]}$ family of sets doesn't have two disjunct elements. Prove, that there is always an $F' \subseteq 2^{[n]}$ family of sets, which contains $F$, $F'$ has no ...
1
vote
0answers
39 views

Is there an upper limit to the number of times a value can occur in a superset?

Given a set of numbers $S=\{-5,6,9,3,2,-2\}$, is there an upper limit to the number of times a particular value (say $4$) can occur in the sums of all the combinations of these numbers? For example: ...
2
votes
1answer
55 views

Counting 5-point, 4-edge subgraphs of a chess board

I don't know graph theory, but I want to study this specific question for a while. I have no idea if this is a well known and studied question or not. I found it very difficult, and I don't know where ...
0
votes
1answer
21 views

Unimodality of sequence

I have to show the following: a) was pretty easy to show, however, I am not able to get something useful out of the recursive definition in b) and I have no idea how to approach c). What bijection ...
2
votes
1answer
47 views

How many non prime factors are in the number $N=2^5 \cdot 3^7 \cdot 9^2 \cdot 11^4 \cdot 13^3$.

to find non prime factors in the number $N=2^5 \cdot 3^7 \cdot 9^2 \cdot 11^4 \cdot 13^3$. First I tried finding all the factors by adding 1 to each of the exponents and then multiplying them and ...
0
votes
1answer
44 views

no. of disordered pairs of disjoint subsets

I found this question in a book. The same question has been asked before, but I want a more generalised and rigorous, so to speak, answer. The question reads- " Consider the set $S= \{1,2,3,4\}.$ ...
0
votes
1answer
57 views

What kind of tree it is? How to solve the problem?

I have a tree with following configuration: n is the number of different vertices v ($0 \lt v \le n$). Each vertice ...
1
vote
1answer
43 views

The greatest number of points of intersection of n circles and m straight lines is-

The question is about combinatorics. I have no idea on how to start solving the problem. Please guide me. $(a) 2mn+ {m \choose 2}$ $(b) \frac{1}{2}m(m-1)+n(2m+n-1)$ $(c) {m \choose 2}+2({n \choose ...
2
votes
2answers
33 views

How do you find the the sum of a list of permutations?

If you are given the digits 1, 2, 3 and 4 and then are asked to find the number of different 4-digit numbers you can make (repetition is allowed). We can multiply $4 \times 4 \times 4 \times 4 = 256$ ...
2
votes
1answer
286 views

Count ways to reach last layer

Consider directed graph which has $N + 2$ layers numbered from left to right by integers from $0$ up to $N + 1$. The leftmost ($0$) and the rightmost ($N + 1$) layers both contain only one vertex ...
1
vote
1answer
119 views

Combinatorial Marble Choosing

A bag contains $3$ red marbles, $3$ green ones, $1$ lavender one, $6$ yellows, and $4$ orange marbles. How many sets of five marbles include either the lavender one or exactly one yellow one but not ...
-4
votes
1answer
31 views

A question on basic combinatorics. [closed]

I wonder in how many ways $n$ women and $n$ men can be sat down a circular table such that no man sits beside a man and no woman sits beside a woman?
2
votes
1answer
292 views

How to prove that if n and k are integers with 1 ≤ k ≤ n, then k*(n C k)=n(n−1 C k−1) combinatorally?

I am having with combinatorial proofs. My professor says to come up with a scenario so that we can connect both sides by double counting but I am clueless.
1
vote
0answers
56 views

Blocks of consecutive natural numbers

Let a < b be natural numbers. Prove that every block of b consecutive natural numbers contains two distinct elements whose product is divisible by ab. Suppose now a < b < c are natural ...
2
votes
1answer
258 views

Number of ways to place $N$ items in $K$ bins where each bin has at least $1$ item?

What is the combinatoric describing the number of ways to place $N$ items in $K$ bins where each bin has at least $1$ item? Is it just $N-1$ choose $K-1$?
0
votes
1answer
28 views

For a solution of linear recurrence relation, $\lim_{n\to\infty}a_n^{1/n}$ is a zero of a related polynomial

On page 134 of J.H. van Lint's book A Course in Combinatorics, it says from $a_n=5a_{n-1}-7a_{n-2}+4a_{n-3}$ $(n\ge5)$, we find that $\lim_{n\to\infty}a_n^{1/n}=\theta$, where $\theta$ is the ...
2
votes
3answers
66 views

The number of choices of 3 kinds of crust and up to 6 distinct toppings

David has a pizza shop. There are 3 kinds of crust and 6 different toppings he can chose from. If customers can have as many toppings as they'd like but may not order double of one topping, how ...
1
vote
1answer
37 views

2x2 grid game problem

A friend of mine is attempting to make a webpage that has a game for a 2x2 grid that is similar to the old North, South, East, West game. I cannot for the life of me figure this out. Essentially, ...
0
votes
1answer
61 views

Each Point in Cirlce

Each point in a circle is colored in one of 3 colors (blue, White, or red). Prove that one can find points that are vertices of an isosceles triangle, and either 3 points are all colored with the same ...
0
votes
1answer
22 views

Rewrite the sum of the products by interpretation

By interpreting what the following sum is counting and then counting the same object in a different way, rewrite the following sum as a product of two terms (without any sum): $\sum\limits_{k=m}^n$ ...
0
votes
1answer
34 views

Some men and women are randomly assigned seats at a round table and no two persons of the same sex are seated next to each other. Probability of this?

Four women and four men are assigned seats at random at a round table. what is the probability that no two persons of the same sex will be sitting next to each other?
0
votes
0answers
44 views

how would i simplify this into an identity?

$$ B_{n,k}^{f\ln(g)} = B_{n,k}\left(\frac{d}{dx}[f(x)\ln(g(x))], \frac{d^2}{dx^2}[f(x) \ln(g(x)), \cdots, \frac{d^{n-k+1}}{dx^{n-k+1}}[f(x) \ln(g(x))]\right) $$ We know that: $$ B_{n,k}^{f\ln(g)} = ...
0
votes
0answers
19 views

How to find the number of words of length $h$ in a subsets $A$?

Let $L=\{0,1\}^*$ (the set of binary words on $0$ and $1$), Given a tuple of words $(w_1,w_2,\cdots,w_n)\in L^n$ and a function $\sigma:[1,n]\to [1,n]$ define the following set: ...
0
votes
2answers
24 views

Permutations; group of 5 boys, 10 girls. What's the probability the person the 4th position is a boy?

Problem description: A group of 5 boys and 10 girls is lined up in random order -- that is, each of the 15! permutations is assumed to be equally likely. What is the probability that the person in ...
1
vote
0answers
44 views

Counting problem of combinations of symmetric matrix.

Given, a symmetric $n*n$ matrix $G$ with 0,1 entries. Each row of has same number of 1. $G$ is arranged in a certain order using a rule. The rule is described below- $G$ is partitioned in to two sub ...
1
vote
1answer
47 views

Binomial Coefficients and Function Composition

I found a paper that stated the following without proof. I tried to prove it on my own, but so far to no avail. Define $\varphi^{+}: \mathbb{N}^2 \to \mathbb{N}$ by $\varphi^{+}(i,j) = i + j$. ...
3
votes
5answers
179 views

Curious Binomial Coefficient Identity

Consider the following set of identities: ${m+1\choose 1}={m\choose 1}+1$, ${m+1\choose 2}=2\binom m 2 - {m-1\choose 2}+1$, ${m+1\choose 3}=3\binom m3-3{m-1\choose 3}+{m-2\choose 3}+1$, ... This set ...
1
vote
2answers
43 views

Consider all the permutations of the word “ENDEANOEL”

Consider all the permutations of the word "ENDEANOEL" : 1)What is the number of permutations containing the word "ENDEA" ? I can't understand how to approach this problem!! 2)Number of permutations ...
0
votes
1answer
20 views

Reverse permutation, number of inversions, descents, major index

If $w=a_1a_2...a_n \in S_n $, then let $w^r=a_n....a_2a_1$, the reverse of $w$. Express inv($w^r$), des($w^r$) and maj($w^r$) in terms inv($w$), des($w$), maj($w$), respectively. It from Stanley's ...
4
votes
1answer
121 views

Complex Analysis proof of multinomial expression

I've recently come across the following identity $$ \displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n} $$ A nice complex analysis proof (by Felix Marin, here) follows as: ...
2
votes
1answer
28 views

How do people find the number of ways you can put together a rubiks cube?

Just curious. How do people actually find the number of ways you can put together a rubiks cube? How do you find the number of choices? Do you use the same permutation formula? Insight would be ...
3
votes
3answers
107 views

Is this permutations or combinations?

I am a bit confused. When we use the multiplicative principle are we finding the number of permutations or combinations. An example of using this principle is where I have $5$ shirts $3$ pairs of ...
0
votes
1answer
36 views

Combination formula?

I know there is a formula for finding the different combinations when you are dividing them in groups: $$\binom{n}{r} = \frac{n!}{(n-r)!\, r!}$$ However, what if you just want to find the number of ...
1
vote
2answers
3k views

number of ordered partitions of integer

Please, help me out How to evaluate the number of ordered partitions of the positive integer 5 Thanks!
0
votes
0answers
21 views

Other than the icosahedron in which each vertex has degree 5, is there any triangulation of the sphere that meets the following three conditions?

Every vertex has degree > 3. There is no separating triangle (a triangle with vertices of the graph both inside and outside the triangle). Every vertex-coloring using exactly four colors consists of ...
2
votes
1answer
104 views

Probability of selecting the winning numbers in a lottery

I've been studying combinatorics for a while. I've solved a problem but I'm not sure if I'm right. I'll just copy-paste the problem here. In a lottery, six distinct numbers are selected at random ...
-1
votes
2answers
24 views

How many ways are there to arrange three of the letters chosen from the set ABCDE? [closed]

Please show your work. I've been looking at this problem for over an hour now and havn't been able to solve it. Thank you!
0
votes
1answer
34 views

Why do (the ranges of) these sequences intersect?

Let $\{(a_n,b_n)\}$, ($1\le n\le N$) be a finite sequence and $\{(s_n,t_n)\}$ ($n\ge 1$) be an infinite sequence, both in $(\{0\}\cup \mathbb{Z}^{+})^2$. We have $a_1=0$ and $b_N=0$. Also, either ...
0
votes
1answer
42 views

Number of paths in a graph with infinite nodes

Does a graph with infinite nodes that is not fully connected have a countably infinite or a uncountably infinite number of paths originating from a single node? We are only concerned with paths that ...
-4
votes
1answer
31 views

Combinatorics Generating Functions [closed]

Any tips/comments would be greatly appreciated! Compute the generating function of the number sequence $h_n = (-2)^n n^2$ where $n\geq 0$.
0
votes
4answers
66 views

Combinatorial Proof of an Instance of the Binomial Theorem

Give a combinatorial proof of the following instance of the binomial theorem. For any positive integer $k$, $(k + 1)^{n}$ = $\sum\limits_{i=0}^{n}$ ${n}\choose{i}$$k^{i}$. I have looked at this for ...
2
votes
0answers
45 views

Coupon collector variation (with deleterious coupons and tolerance)

Imagine the standard coupon collector's problem, with n coupons to be collected. However, the sample space also contains T bad coupons. Specifically, if during the collection, I collect more than t (t ...
0
votes
1answer
41 views

Generating function of derangements

I am pretty new to the topic of generating functions and I would appreciate if someone could help me out with this problem I have. In the lecture we have proven the following generating function for ...
0
votes
2answers
20 views

Prove that if $k\mid n$ then $p(A_k)={1\over k}$

Let $n$ be a natural number, $n=p_1^{a_1}\cdot...\cdotp_m^{a_m}$. Let us randomly choose a number between 1 and $n$ with a uniform, equal chance. Let us denote the event "The number chosen is ...
-5
votes
1answer
34 views

Need help in solving [closed]

A group of $60$ children attend an after school club. Of these, $35$ children play football and $29$ play hockey. Three children do not play either football or hockey. Find the number of children ...
1
vote
1answer
48 views

How many solutions of equation

How many solutions of equation $x_1+x_2+x_3+x_4=n$ in $N_0$ such that $x_1\leq x_2\leq x_3 \leq x_4$? I found solutions of $x_1+x_2+x_3=n$ in $N_0$ , $x_1\leq x_2\leq x_3 $ in the following way : ...