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
1answer
55 views

Need help regarding String Derangements using Inclusion/Exclusion

I have this question that states: Using Inclusion/exclusion, find the number of derangements of each of the following strings. A) aabcd B) aabbcc I understand inclusion/exclusion I just don't ...
2
votes
1answer
83 views

How to prove the equivalence of the two functions?

$$f_1(k,n):=\sum_{0\leqslant v\leqslant n}\dfrac{\left(2(k+v)\right)!}{(k+v)!v!(2k+v)!(n-v)!2^v}, \quad k,n \in \mathbb{N} $$ $$ f_2(k,n):=\sum_{0\leqslant m\leqslant ...
1
vote
1answer
164 views

Combinations without repeating pairings more than twice.

How many groups of 10 can one make from 100 people if no pairing is repeated more than twice? You are making teams for a series of icebreaking exercises. You want to force patrons to meet other ...
3
votes
1answer
31 views

Euler Number/Polynomial Identity

If Euler numbers are defined as $$\frac{1}{\cosh{x}}=\frac{2}{e^x+e^{-x}}=\sum_{n=0}^\infty{E_n\frac{x^n}{n!}}$$ and Euler polynomials are defined as ...
1
vote
1answer
60 views

5 balls - which one has the middle weight?

I'm looking for some help. It's one riddle, and i'm not sure, if my solution is the best one We have 5 balls. Every ball has different weight. You have scales, which tells you, which ball is heavier. ...
0
votes
2answers
130 views

Lottery payout with organizer margin.

Assume we have a lottery with payouts like this $(1,2,3,4,5,25,30,100)$ So you buy a ticket and you can win a pot which will multiply your ticket price by the numbers written ahead. The organizer ...
0
votes
2answers
38 views

Game of Bridge probability

In a game of bridge, choose 13 cards from a deck at random (use equally likely probability). Question: What is the probability you get NO spades? What is the probability you get no card higher than 9 ...
0
votes
1answer
65 views

How to make this problem combinatorial and challenging?

Assume we have 9 positive real numbers \begin{align}&SNR_{11},SNR_{12},SNR_{13}\\&SNR_{21},SNR_{22},SNR_{23}\\&SNR_{31},SNR_{32},SNR_{33} \end{align} The question is how can I ...
0
votes
0answers
34 views

Calculating total number of possible passwords with rules regarding amount of certain characters (Cont.)

I recently posted a question regarding the total amount of passwords/words when applying certain rules. These rules were: Exactly 10 characters long Will contain exactly 6 letters (a-f, all ...
0
votes
1answer
32 views

Find $k$-th derivative of $g(t)=e^{Cf(t)}$?

Is there a formula for findind the $k$-th derivative of a function like $g(t)=e^{Cf(t)}$? I'm trying to deduce it and I got to the conclusion I could write something like ...
3
votes
0answers
33 views

write down a concrete 2-coboundary

Let $G=SL_3(\mathbb{Z})$, the group of 3 by 3 matrices with determinant 1. Then by a deep theorem of Borel and Serre proved in this paper "Corners and arithmetic groups", we know that the 2nd ...
0
votes
0answers
24 views

Bell polynomials using multi-index notation?

In combinatorics the Bell polynomials are a triangular array of polynomials given by: \begin{align*} \displaystyle B_{n, k}(x_1, x_2, \ldots, x_{n-k+1})=\sum \frac{n!}{j_1!j_2!\cdots ...
0
votes
0answers
20 views

Constrained sums of conditional multivariate hypergeometric distributions

My first post on math.stackexchange so please let me know if it is a poor one. I am developing a method for making a map using an MCMC algorithm. Each pixel in a map can one of a set of possible land ...
0
votes
0answers
20 views

Place 18 coins into a 6x4 grid so all columns and rows are even [duplicate]

My son has been set a maths challenge that I believe to be impossible. However, he's been told there are 8 ways to do it. Having spent an hour with an increasingly frustrated six year old, we think we ...
0
votes
1answer
155 views

2^m marbles in multiple boxes.

Let m be a non-negative integer. Suppose $2^m$ marbles are separated into several boxes. At each step we are allowed to do the following operation: Pick two boxes, say box A with p marbles and box B ...
0
votes
0answers
54 views

Balls into bins with repelling balls and bins, probability 1 or more of a specified subset of bins is empty?

I have $N$ sets of differently colored balls, each set a distinct color and each set consisting of 3 balls. There are 9 bins. Balls are tossed and will land into bins uniformly randomly, except if ...
1
vote
1answer
38 views

Cycle index of a symmetric group defined by recurrence relation

It is claimed in a text I am reading that the cycle index of the symmetric group satisfies the recurrence relation $$Z(S_n)=n^{-1} \sum_{k=1}^n{s_kZ(S_{n-k})}$$ This is presented without explanation, ...
0
votes
1answer
23 views

How many decompositions $k=\jmath_1+\ldots+\jmath_k$ are there?

Let $k$ be a non-negative integer. How many decompositions of $k$ as a sum $\jmath_1+\ldots+\jmath_k$ of non-negative integers are there? I didn't mistype $\jmath_k$. Each permutation of the ...
2
votes
1answer
87 views

How to check if any subset of a given set of numbers can sum up to a given number

Given a number, say $x$, and a set of numbers made up of only $k$ different numbers, where each of the $k$ numbers is repeated $n_1,n_2,\dots n_k$ times. How do I tell if it is possible to find a ...
2
votes
3answers
106 views

Probability All Players Receive a Spade

52 cards were distributed among 4 players, 13 cards for each. Calculate the probability that all players have received at least one spade. I do not know what to do with this question, i have the ...
1
vote
1answer
113 views

How many telephone numbers that are seven digits in length have exactly five 6's?

How many phone numbers that are seven digits in length, have exactly five 6's? My attempt: {{6,6,6,6,6}{ , }} $(5(top) 5(bottom)) * (18(top) 2(bottom)) = 153$ my reasoning is that the first subset ...
0
votes
1answer
29 views

Card Game: Probability, Combinatorics, - 52 suit picks,12 correct, four suit, not dependant

Using a standard deck of cards (52 cards, four suits), one card is picked to guess the correct suit only and then replaced with the deck shuffled. This is repeated 52 times. If 12 cards out of the ...
2
votes
2answers
149 views

How many five-digit numbers do not have three consecutive digits the same?

How many five-digit numbers do not have three consecutive digits the same? Also, the initial digits might be $0$, but I'm not sure how that changes the answer. This is the formula I've come up with ...
0
votes
0answers
13 views

Finding the next k-permutation of n

I have a set of numbers say $\{x_1, x_2, x_3, x_4, x_5, ... x_n\}$ and a number $k$. We can form $n!/(n-k)!$ permutations using this. My question is: Suppose $n = 5$ and the set of numbers is like ...
0
votes
1answer
29 views

The number of ways to distribute groups between professors. Combinatorics. Surjective problem?

I supposed that I could use Stirling numbers to solve the following problem. So S(m, k) where m = 7 and k = 5 would be 140. But it appears to be wrong. There are 5 professors of biology and 7 ...
3
votes
3answers
109 views

Asymptotic of a sum involving binomial coefficients

Could you help me to find an asymptotic for this sum? $$ \sum_{k=0}^{n - 1} (-1)^k {n \choose k} {3n - k - 1 \choose 2n - k} = {n \choose 0} {3n - 1 \choose 2n} - {n \choose 1} {3n - 2 \choose 2n - ...
0
votes
2answers
54 views

number of ordered pair subsets $B$ and $C$ of $A$ such that $B$ and $C$ have exactly one element in common

My question is Let $A=\{1,2,3,4,5,6\}$, then what is the number of ordered pairs of subsets $B$ and $C$ of $A$ such that $B$ and $C$ have exactly one element in common?
1
vote
3answers
98 views

Find the number of integer solutions for $x_1+x_2+x_3 = 15$ under some constraints by IEP.

For equation $$ x_1+x_2+x_3 = 15 $$ Find number of positive integer solutions on conditions: $$ x_1<6, x_2 > 6 $$ Let: $y_1 = x_1, y_2 = x_2 - 6, y_3 = x_3$ than, to solve the problem, equation ...
0
votes
0answers
29 views

How many sets of cardinality $n$ there are in the $\mathcal{P}(S)$ if $|S|=m$?

How many sets of cardinality $n$ there are in the $\mathcal{P}(S)$ if $|S|=m$? and $n \leq m$ For example 10 subsets of cardinality 3 can be obtained from a set of cardinality 5. But I would like to ...
0
votes
1answer
42 views

Probabilty of choosing at least one ball from different boxes

Assume that we have 3 different boxes: A, B and C. Let $n_A, n_B$ and $n_C$ denotes the number of balls in each box. After each selection, the ball will be put back before the next selection. Let ...
1
vote
1answer
32 views

Did the teams cheat at this charity golf tournament?

I was at a charity golf tournament yesterday, run by a very well known Fortune 100 company. There were 4 golf courses at the club. On each golf course there were 36 teams playing, so a total of 144 ...
1
vote
1answer
53 views

On exponential generating function

In an example in my textbook, it is mentioned that the sequence generated by: ${f(x)= e^x + x^2}$ is: 1,1,3,1,1,1,1,... why is it that when $x^2$ is added to $\sum_{i=0}^{\infty} x^i/i!$ we would ...
1
vote
1answer
196 views

Tile a 1 x n walkway with 4 different types of tiles…

Suppose you are trying to tile a 1 x n walkway with 4 different types of tiles: a red 1 x 1 tile, a blue 1 x 1 tile, a white 1 x 1 tile, and a black 2 x 1 tile a. Set up and explain a recurrence ...
1
vote
1answer
37 views

On partition of integers

I came across an example in my textbook where it was asked to find the generating function for the number of integer solutions of: ${2w+3x+5y+7z=n}$ where ${0\le w, 4\le x,y, 5\le z}$ The ...
0
votes
1answer
39 views

How many ways can 10 identical buttons, 10 identical bows, and 10 identical beads be distributed to 4 different people?

Question: How many ways can 10 identical buttons, 10 identical bows, and 10 identical beads be distributed to 4 different people? My thoughts: I decided to use the bars and stars method. With the ...
12
votes
1answer
240 views

Is there a better bound than $(n^2)^{n^3}$ for the order of the commutator subgroup of a group whose center has index $n?$

Let $G$ be a group and $[G:Z(G)]=n<\infty,$ where $Z(G)$ is the center of $G$. A theorem says that in this case $$o([G,G])\leq(n^2)^{n^3}, $$ where $o(\cdot)$ denotes order and $[G,G]=G'$ is the ...
2
votes
0answers
25 views

How can I find replace exhaustive search to find my optimal solution?

Assume I have two sets each of cardinality $N$. My first goal is to pair the two sets such that no element in set 1 is paired twice with any element of set two! Thanks to the answer provided to the ...
-1
votes
1answer
107 views

Total number of combinations for pairing from two different sets

Assume we have two sets of numbers {1, 2, 3} and {4,5,6}. My aim is to pair two numbers together from the two different sets such as {1} with {4} {2} with {5} {3} with {6} another pairing ...
0
votes
1answer
29 views

Shifted Catalan Recurrence

I am trying to find a recurrence for a seqence $t_n$ which is given n points on a circle, the number of ways to pair any number of them by noncrossing chords and color the remaining with 2 colors. I ...
1
vote
1answer
92 views

How many combinations of passwords can be created according to these conditions

Suppose that a password must have at least $8$, but not more than $10$ characters, where each character in the password is either one of the $26$ lower case English letters, or one of the $10$ ...
0
votes
1answer
69 views

Probability of getting at least 4 numbers by rolling dice n times

I want to compute probability of getting at least 4 numbers by rolling dice n times. Now my formula is $$ P = \frac{6^n - 2^n * {6 \choose 2} + 4 * 1^n * {6 \choose 1}}{6^n} $$ But by principle of ...
9
votes
1answer
451 views

How would I go about proving this expression?

Expression: $$ \sum_{c=1}^{n-1} \sum_{k=c+1}^{n} \sum_{j=0}^{min\{c,k-c\}} {c \choose j} \frac{(k-c)!}{(k-c-j)!} f^{k-c-j} g^{c-j} B_{n,k}^{(g \diamond f)^c}(x) =$$ $$ \sum_{w=1}^n \sum_{m_1=1}^w ...
0
votes
1answer
17 views

Compositions of $n$ with $r$ parts for every possible $r$ with parts no greater than 6 using generating function

I am starting with a generating function of the form $(x+x^2+x^3+x^4+x^5+x^6)^r$. I believe this is the correct approach but need a generating function that is a ratio of two polynomials.
2
votes
1answer
46 views

(Enumeration) In how many ways can 5 people be placed in 8 rooms

In how many ways can 5 people be put into 8 rooms if only 2 of the people (very dubious characters) can’t share a room with anyone? Note that there is no maximum capacity for the rooms. My attempt: 2 ...
0
votes
1answer
17 views

Generating function from convolution

I have a generating function $T(x) = \sum_{n \geq 0} t_nx^n$ and from a recurrence of $t_n$ I have $\sum_{n \geq 1} t_nx^n = \sum_{n \geq q} 2t_{n-1}x^n + \sum_{n\geq1} (\sum_{k=1}^{n-1} ...
3
votes
2answers
73 views

Distance between two positions of the rubik cube .

It's now known that to reach the solved position of the rubik cube from any other position you need at most $20$ moves (a $180^{\circ}$ of a face is counted as one move , not two ) . See for example ...
1
vote
0answers
23 views

How is inequality/approximation obtained?

I am reading on combinatorics - probabilistic methods. In one particular problem I came across the inequality $$\binom{n}{k}(1-2^{-k})^{n-k} < n^k e^{-(n-k)2^{-k}}$$ I understand that ...
0
votes
0answers
19 views

What's a good book that touches on computational complexity theory and combinatorics?

I'm taking a class in enumerative combinatorics. The professor focusses on the complexity of solving combinatorics problems like partitions etc. I'm using Enumerative Combinatorics but it does not ...
0
votes
0answers
28 views

number of permutations with only odd length cycles [duplicate]

Can someone please show me a combinatorical way to find this number (number of permutations of n objects with only odd length cycles ? i found it only by generating function - but i wonder if there is ...
4
votes
2answers
92 views

What is the number of distinct 3 letter words out of different number of given letters?

Question What is the number of distinct 3 letter words out of the following: a number of distinct Rs ...